class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
 
        //prev指向被打印过的节点
        TreeNode prev = null;
        //注意这里的循环条件
        //因为后续cur为空时要弹出栈顶元素，故栈不能为空
        //且一开始时栈为空，故cur不为空就可进入循环
        //当栈空且cur为空，说明前序遍历已完成
        while (cur != null || !stack.isEmpty()) {
            //cur走左子树
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
 
            //当cur为空时，不可直接将栈顶元素弹出和添加进顺序表
            //要判断栈顶元素（根节点）是否有右孩子
            //若右孩子为空可以弹出和添加
            //若右孩子不为空，需要先将右子树的元素入栈并添加
            TreeNode top = stack.peek();
            //当栈顶元素的右孩子入过栈时，此时栈顶元素可以弹出并添加进顺序表
            if(top.right == null || top.right == prev) {
                stack.pop();
                list.add(top.val);
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return list;
    }
}